// @coding: utf8

#include <iostream>
#include <vector>
#include <algorithm>
#include <random>

// @brief 快速排序
// 算法思想：找到一个基准值，然后使用两个游标向中间逼近，相交后将基准值放到交点同时保证left的都小于基准值，right都大于基准值
void quick_sort(int* data, int left, int right)
{
    // 长度小于1直接返回
    if (left >= right)
        return;
    // 找到基准值
    int base_value = data[left];
    int left_idx = left;
    int right_idx = right;
    while (left_idx < right_idx)
    {
        // 保证右边的值都不小于基准
        while (left_idx < right_idx && data[right_idx] > base_value) right_idx--;
        // 保证左边的值都不大于基准
        while (left_idx < right_idx && data[left_idx] <= base_value) left_idx++;
        std::swap(data[left_idx], data[right_idx]);
    }
    // 吧基准值移动到left_idx为止，这样数据分为三段
    // [left, left_idx - 1]  left_idx  [left_idx + 1, right]
    // 将第一段和第三段继续递归排序
    std::swap(data[left], data[left_idx]);
    quick_sort(data, left, left_idx - 1);
    quick_sort(data, left_idx + 1, right);
}

void dump_vector(std::vector<int>& vec)
{
    std::cout << "dump_vector: " << std::endl;
    for (auto n : vec)
    {
        std::cout << n << ",";
    }
    std::cout << std::endl;
}

int main()
{
    std::random_device rand_device;
    //std::uniform_int_distribution<int> dist(0, 9);
    std::mt19937 rand_gen(rand_device());
    std::vector<int> vec;
    std::vector<int> vec_verify;
    std::vector<int> vec_result;
    int cnt = 16;
    vec.reserve(16);
    for (int idx = 0; idx < cnt; ++idx)
    {
        vec.push_back(rand_gen());
    }
    vec_verify = vec;
    vec_result = vec;

    dump_vector(vec);
    std::sort(vec_verify.begin(), vec_verify.end());
    dump_vector(vec_verify);
    quick_sort(vec_result.data(), 0, vec_result.size() - 1);
    dump_vector(vec_result);
    bool result = std::equal(vec_result.begin(), vec_result.end(), vec_verify.begin(), vec_verify.end());
    if (!result)
    {
        std::cout << "faild, test data is: " << std::endl;
        dump_vector(vec);
    }
    else
        std::cout << "passed" << std::endl;

    return 0;
}